package com.zdp.leetcodeMiddle;


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/*
* 题目描述：
* 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
注意:

S 只包含小写字母并且长度在[1, 500]区间内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorganize-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 重构字符串_767 {
    public static void main(String[] args) {
        重构字符串_767 demo = new 重构字符串_767();
        String aab = demo.reorganizeString("vvvlo");
        System.out.println(aab);
    }


    /*
    *  利用大根堆  按照字符出现的次数排序
    *  每次拿出最大的两个字符进行组合 （ 保证不相邻）
    * 当大根堆中元素为空，字符构造完毕
    *  S.length() +1 /2 为 每个字符最多的出现次数
    * */
    public String reorganizeString(String S) {
        int[] words = new int[26];
        int maxCount = 0 ;
        for(int i =0 ; i <S.length(); i++){
            words[S.charAt(i) - 'a'] ++;
            maxCount = Math.max(maxCount,words[S.charAt(i) - 'a']);
        }
        if( maxCount > (S.length() +1) /2){
            return "";
        }
        // 根据 字符出现的次数进行排序
        // 默认为小根堆  我们需要大根堆  自定义排序规则 来创建大根堆
        PriorityQueue<Character> queue = new PriorityQueue<>(new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                return words[o2-'a'] - words[o1-'a'];
            }
        });
        // 将字符加入大根堆
        for(char c = 'a';c<='z' ; c++){
            if(words[c-'a'] > 0){
                queue.offer(c);
            }
        }
        // 重构字符串
        StringBuilder result = new StringBuilder();
        while(queue.size() > 1){ // 每次都是两个两个取， 如果字符串长度为奇数，那么还会剩下一个
            char letter1 = queue.poll();
            char letter2 = queue.poll();
            result.append(letter1);
            result.append(letter2);

            words[letter1 - 'a'] --;
            words[letter2 - 'a'] --;
            // 判断这两个字符的次数是否大于0 如果大于 继续加入大根堆
            if( words[letter1 - 'a'] > 0){
                queue.offer(letter1);
            }
            if( words[letter2 - 'a'] > 0){
                queue.offer(letter2);
            }
        }
        if( queue.size() > 0){
            result.append(queue.poll());
        }

        return result.toString();
    }
}
